
//我们这里考虑正则表达式
//四个操作，1就是匹配，2，or，就是一个或的操作，3,*,代表重复，4.括号
//通过上面四个基本操作，可以实现各种各样的通配符，符号匹配效果
//关于DFA和NFA
//让我们来考虑一下如何模拟NFA
//NFA的表示，0到M的数字表示状态，M是正则表达式的长度，多的一个用来表示接受状态
//match-transition，用数组存储正则表达式并表示这种转换
//3-transition，存储在有向图中
//维护NFA所有可能的状态
//和在学怎么用DFA模拟NFA的时候是一样的，那时候是把一个个可能变成一个个集合，然后每次读取的转换就是一个可能集合到另一个可能集合的转换
//现在也是一样，现在是维护一个可能集合，然后通过有向图进行转换去得到下一个可能集合，直到最终得到了接受的可能集合或者拒绝了
//构建NFA：*需要三个3-transition，从被*的到*，*再到被*的，和*到*后面的
//or需要两个3-transition，从or前面的头到or后面的头，和or前面的尾到or后面的尾
//可以维护一个栈去实现or和括号
//记得前面用数组存储正则表达式，这里的栈只需要存储数组的下标就可以了、
//这里的时间和空间复杂度都是线性的
//在应用中比较出名的是grep，就是终端那个管道过滤，更多的通配符也可以在这个基础上进行实现
//这种东西有很多库函数,但是有时候库的性能很差，要学会自己去看，自己去写
//还可以用来采集DNA模板以及用于网络爬虫等
//正则表达式不是无所不能的
//计算理论是编译器等的基础
import edu.princeton.cs.algs4.Digraph;
import edu.princeton.cs.algs4.DirectedDFS;

import java.util.Stack;

import edu.princeton.cs.algs4.Bag;;

public class NFA {
  private Digraph G; // digraph of epsilon transitions
  private char[] re; // regular expression
  private int M; // number of characters in regular expression
  // Create the NFA for the given RE

  public NFA(String regexp) {
    M = regexp.length();
    re = regexp.toCharArray();
    G = buildEpsilonTransitionDigraph();
  }

  // 根据构建的NFA识别字符串
  // 维护NFA所有可能的状态
  // 和在学怎么用DFA模拟NFA的时候是一样的，那时候是把一个个可能变成一个个集合，然后每次读取的转换就是一个可能集合到另一个可能集合的转换
  // 现在也是一样，现在是维护一个可能集合，然后通过有向图进行转换去得到下一个可能集合，直到最终得到了接受的可能集合或者拒绝了
  // 1，用pc和dfs构建初始可能集合
  // 2. 大循环读取字符串
  // 3. 里面每次都构建新的状态集合，新的状态集合由旧状态集合先读取输入进行普通转换，再由新状态集合自己dfs加入epsilon转换得到新状态集合
  // 4. 结束之后看看可能集合里有没有接受状态，有的话就成功了
  public boolean recognizes(String txt) {
    Bag<Integer> pc = new Bag<Integer>();
    pc.add(0);
    DirectedDFS dfs = new DirectedDFS(G, 0);
    for (int i = 0; i < G.V(); i++) {
      if (dfs.marked(i)) {
        pc.add(i);
      }
    }

    for (int i = 0; i < txt.length(); i++) {
      Bag<Integer> states = new Bag<Integer>();
      for (Integer state : pc) {
        if (state == M) {
          continue;
        }
        if (re[state] == txt.charAt(i) || re[state] == '.') {
          states.add(state + 1);
        }
      }
      dfs = new DirectedDFS(G, states);
      pc = new Bag<Integer>();
      for (int j = 0; j < M; j++) {
        if (dfs.marked(j)) {
          pc.add(i);
        }
      }
    }

    for (Integer v : pc) {
      if (v == M) {
        return true;
      }
    }
    return false;
  }

  // 构建NFA：*需要三个ϵ-transition，从被*的到*，*再到被*的，和*到*后面的
  // or需要两个ϵ-transition，从or前面的头(也就是'(')到or后面的头(or后第一个)，和or到or后面的尾（也就是')'）
  // 可以维护一个栈去实现or和括号
  // 记得前面用数组存储正则表达式，这里的栈只需要存储数组的下标就可以了、
  // 括号也得加epsilon转换到下一个状态
  private Digraph buildEpsilonTransitionDigraph() {
    Stack<Integer> stack = new Stack<Integer>();
    Digraph G = new Digraph(M + 1);
    for (int i = 0; i < M; i++) {
      int lp = i;
      if (re[i] == '(' || re[i] == '|') {
        stack.push(i);
      } else if (re[i] == ')') {
        int or = stack.pop();
        if (re[or] == '(') {
          lp = or;
        } else {
          lp = stack.pop();
          G.addEdge(lp, or + 1);
          G.addEdge(or, i);
        }
      }
      if (i < M - 1 && re[i + 1] == '*') {
        G.addEdge(i + 1, lp);
        G.addEdge(lp, i + 1);
      }
      if (re[i] == ')' || re[i] == '(' || re[i] == '*') {
        G.addEdge(i, i + 1);
      }
    }
    return G;
  }

  public static void main(String[] args) throws Exception {
    System.out.println("Hello, World!");
  }
}
